package leetcode.editor.cn;

import java.util.HashMap;
import java.util.Map;

/**
 * @author: yangwk
 * @date: 2023/3/8
 * @description:
 **/
public class P1061 {
    public static String smallestEquivalentString(String s1, String s2, String baseStr) {
        int length = s1.length();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < length; i++) {
            map.put(s1.charAt(i), i);
            map.put(s2.charAt(i), i + length);
        }
        UF uf = new UF(26);
        for (int i = 0; i < length; i++) {
            Integer integer1 = map.get(s1.charAt(i));
            Integer integer2 = map.get(s2.charAt(i));
            uf.union(integer1, integer2);
        }
        int baseLength = baseStr.length();
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < baseLength; i++) {
            char c = baseStr.charAt(i);
            Integer position = map.get(c);
            Character minChar = c;
            if (position != null) {
                for (Map.Entry<Character, Integer> entry : map.entrySet()) {
                    Character key = entry.getKey();
                    Integer value = entry.getValue();
                    if (uf.isConnected(value, position)) {
                        if (minChar.compareTo(key) > 0) {
                            minChar = key;
                        }
                    }
                }
            }
            stringBuilder.append(minChar);
        }
        return stringBuilder.toString();
    }

    public static void main(String[] args) {
        String s1 = "leetcode";
        String s2 = "programs";
        String baseStr = "sourcecode";
        System.out.println(smallestEquivalentString(s1, s2, baseStr));
    }

    public static class UF {
        int[] num;
        int[] size;

        public UF(int n) {
            num = new int[n];
            size = new int[n];
            for (int i = 0; i < num.length; i++) {
                num[i] = i;
                size[i] = 1;
            }
        }

        public boolean isConnected(int v, int w) {
            int root1 = findParent(v);
            int root2 = findParent(w);
            return root1 == root2;
        }

        public int findParent(int v) {
            if (num[v] != v) {
                v = findParent(num[v]);
            }
            return v;
        }

        public void union(int v, int w) {
            int parent1 = findParent(v);
            int parent2 = findParent(w);
            if (parent1 == parent2) {
                return;
            }
            if (size[parent1] > size[parent2]) {
                size[parent1] += size[parent2];
                num[parent2] = parent1;
            } else {
                size[parent2] += size[parent1];
                num[parent1] = parent2;
            }

        }

    }
}
